#include <stdio.h>
#include <stdlib.h>
/*
二叉排序树特性：
1. 左子树所有节点值 < 根节点值
2. 右子树所有节点值 > 根节点值
3. 左、右子树也为二叉排序树
*/

typedef int ElementType; // 定义元素类型为int

// 二叉树节点结构体：包含数据、左孩子指针、右孩子指针
typedef struct TreeNode {
    ElementType data;           // 节点存储的数据
    struct TreeNode* left_child; // 指向左子树的指针
    struct TreeNode* right_child; // 指向右子树的指针
} TreeNode;

typedef TreeNode* BinTree; // 简化二叉树类型为 TreeNode*

// 树的数组表示（-1 表示对应位置为“空节点”）
int treeArr[] = {70,55,49,30,-1,39,-1,-1,53,-1,-1,-1,80,75,-1,-1,98,95,-1,-1,-1}; 
ElementType idx = 0; // 全局索引（前序创建树时遍历数组用）

// 前序遍历创建二叉树：从数组 treeArr 按“根-左-右”顺序递归构建
void CreateTree(BinTree* T) {
    ElementType num;
    num = treeArr[idx++]; // 读取数组当前元素，并将索引后移
    if (num == -1) { // 若元素为 -1，说明当前节点为空
       *T = NULL;    // 将当前子树置为空
    }
    else {
        *T = (BinTree)malloc(sizeof(TreeNode)); // 为当前节点分配内存
        (*T)->data = num;                       // 设置节点数据
        CreateTree(&(*T)->left_child);          // 递归创建左子树
        CreateTree(&(*T)->right_child);         // 递归创建右子树
    }    
}

// 先序遍历二叉树（根→左→右）：验证树是否创建成功
void PreOrderTraversal(BinTree T) {
    if (T == NULL) { // 节点为空时递归终止
        return;
    }
    printf("%d ", T->data);  // 访问当前节点（输出数据）
    PreOrderTraversal(T->left_child);  // 递归遍历左子树
    PreOrderTraversal(T->right_child); // 递归遍历右子树
}


/*
* 参数说明：
* T:         当前子树的根节点
* value:     要查找的值
* parent:    当前节点的父节点（插入时需记录父节点）
* pos:       存储“查找结果节点”的指针（找到的节点 / 合适的父节点）
* 返回值:    找到返回 1，未找到返回 0
*/
// 在二叉排序树中递归查找元素：根据值大小决定在左/右子树继续查找
int SearchBST(BinTree T, ElementType value, BinTree parent, BinTree *pos) {
    if (T == NULL) { // 树为空或递归到空节点，查找失败
        *pos = parent; // 记录父节点（供插入操作使用）
        return 0;      // 返回 0 表示未找到
    }
    if (T->data == value) { // 找到目标节点
        *pos = T;           // 记录目标节点到 pos
        return 1;           // 返回 1 表示找到
    }
    if (T->data > value) { // 目标值 < 当前节点值 → 去左子树查找
        return SearchBST(T->left_child, value, T, pos);
    }
    else { // 目标值 > 当前节点值 → 去右子树查找
        return SearchBST(T->right_child, value, T, pos);
    }
}

// 向二叉排序树插入元素：先查找插入位置，未找到则创建新节点插入
int InsertBST(BinTree* T, ElementType value) {
    BinTree parent, pos;
    BinTree curr;

    // 调用 SearchBST 查找 value 位置，pos 存储“父节点/目标节点”
    int status = SearchBST(*T, value, NULL, &pos); 
    if (status == 0) { // status=0 → 未找到 value，需要插入
        curr = (BinTree)malloc(sizeof(TreeNode)); // 为新节点分配内存
        curr->data = value;           // 设置新节点数据
        curr->left_child = NULL;      // 新节点初始无左右子树
        curr->right_child = NULL;
        if (pos == NULL) { // pos=NULL → 原树为空
            *T = curr;     // 新节点作为根节点
        } else if (value < pos->data) { // 新值 < 父节点值 → 插为左孩子
            pos->left_child = curr; 
        } else { // 新值 > 父节点值 → 插为右孩子
            pos->right_child = curr; 
        }
        return 1; // 插入成功，返回 1
    } else { // status=1 → 已存在 value，插入失败
        return 0;
    }
}

// 删除二叉排序树节点（分三种情况处理）
/*
* 情况1：叶子节点（无左右孩子）→ 直接删除
* 情况2：单孩子节点（仅左/右孩子）→ 孩子顶替自己的位置
* 情况3：双孩子节点 → 用“左子树最大值”或“右子树最小值”代替自己
*/
int Delete(BinTree *d) {
    BinTree temp, record;
    // 情况1：仅左子树（右子树为空）
    if ((*d)->right_child == NULL) {
        temp = *d;         // 暂存要删除的节点
        *d = (*d)->left_child; // 左孩子顶替当前节点位置
        free(temp);        // 释放原节点内存
    }
    // 情况2：仅右子树（左子树为空）
    else if ((*d)->left_child == NULL) {
        temp = *d;         // 暂存要删除的节点
        *d = (*d)->right_child; // 右孩子顶替当前节点位置
        free(temp);        // 释放原节点内存
    }
    // 情况3：左右子树都有 → 找“左子树最大值（最右侧节点）”替换
    else {
        temp = *d;               // temp 记录“替换节点的父节点”
        record = (*d)->left_child; // 从左子树的根开始找
        // 循环找左子树最右侧节点（左子树最大值）
        while (record->right_child != NULL) { 
            temp = record;           // 更新父节点记录
            record = record->right_child; // 向右子树深入
        }
        (*d)->data = record->data; // 用左子树最大值替换当前节点值
        // 删除“用于替换的节点（record）”
        if (temp != *d) {
            // 若替换节点是 temp 的右孩子 → 衔接其左子树（右子树必为空）
            temp->right_child = record->left_child;
        } else {
            // 若替换节点是当前节点的左孩子 → 衔接其左子树
            temp->left_child = record->left_child;
        }
        free(record); // 释放替换节点的内存
    }
    return 1; // 删除成功
}

// 递归查找并删除指定值的节点：找到后调用 Delete 处理
int delete_bst(BinTree *T, int value) {
    if (*T == NULL) { // 树为空，无节点可删
        printf("not found!\n");
        return 0;
    } else {
        if ((*T)->data == value) { // 找到目标节点，调用 Delete 删除
            return Delete(T);
        } else if ((*T)->data > value) { // 目标值小 → 去左子树找
            return delete_bst(&(*T)->left_child, value);
        } else { // 目标值大 → 去右子树找
            return delete_bst(&(*T)->right_child, value);
        }
    }
}

int main() {
    BinTree T; // 定义二叉树根节点指针
    CreateTree(&T); // 前序遍历创建二叉树

    PreOrderTraversal(T); // 先序遍历，验证树创建结果
    printf("\n");

    BinTree searchT; // 存储查找结果的指针
    SearchBST(T, 39, NULL, &searchT); // 查找值为 39 的节点
    printf("查找结果: %d\n", searchT->data); // 输出查找结果

    InsertBST(&T, 99); // 插入值为 99 的节点
    PreOrderTraversal(T); // 先序遍历，查看插入后结果
    printf("\n");

    delete_bst(&T, 49); // 删除值为 49 的节点
    PreOrderTraversal(T); // 先序遍历，查看删除后结果
    printf("\n");
    return 0;
}